/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2018年09月01日
*   描    述：
*   
================================================================*/


#include <iostream>
#include <vector>

using namespace std;

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param inorder: A list of integers that inorder traversal of a tree
     * @param postorder: A list of integers that postorder traversal of a tree
     * @return: Root of a tree
     */
    TreeNode * buildTree(vector<int> &inorder, vector<int> &postorder) {
        // write your code here
        return build(0, inorder.size()-1, 0, postorder.size()-1, inorder, postorder);
    }
    
    TreeNode* build(int in_l, int in_r, int post_l, int post_r, vector<int> &inorder, vector<int> &postorder){
        if( in_r < in_l || post_r < post_l )
            return NULL;

        int i = 0;
        int target = postorder[post_r];
        for(i; i <= in_r - in_l; i++ ){
            if( inorder[in_l + i] == target )
                break;
        }

        TreeNode* root = new TreeNode(target);
        root->left = build(in_l, in_l+i-1, post_l, post_l+i-1, inorder, postorder);
        root->right = build(in_l+i+1, in_r, post_l+i, post_r-1, inorder, postorder);

        return root;
    }

};

